#include<iostream>
#include<stack>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    bool find(TreeNode* sub, TreeNode* x)
    {
        if (sub == nullptr)
            return false;
        return sub == x || find(sub->left, x) || find(sub->right, x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> stP;
        stack<TreeNode*> stQ;
        TreeNode* cur = root;
        while (cur)
        {
            stP.push(root);
            if (find(root->left, p))
                cur = cur->left;
            else
                cur = cur->right;
        }
        cur = root;
        while (cur)
        {
            stQ.push(root);
            if (find(root->left, q))
                cur = cur->left;
            else
                cur = cur->right;
        }

        while (stP.size() != stQ.size())
        {
            if (stP.size() > stQ.size())
                stP.pop();
            else
                stQ.pop();
        }
        while (stP.top() != stQ.top())
        {
            stP.pop();
            stQ.pop();
        }

        return stP.top();
    }
};
int main()
{
    TreeNode* root;
    stack<int> stP;
    stP.push(4);
    stP.push(3);
    stP.push(2);
    stP.push(1);
    while (!stP.empty())
    {
        cout << stP.top() << " ";
        stP.pop();
    }
}